This invention is in the field of digital image data handling, and more specifically is a method of rotating an image by any whole number multiple of ninety degrees.
It is frequently necessary to rotate an image by 90 or 270 degrees, or to form the mirror image of these. The obvious way to do this is to write an image into a memory in one direction and read it out in the orthogonal direction. For example, sixteen words, each of sixteen bits, could be written into a memory, and then sixteen words could be read out, the first output word containing the first bit of each input word, the second output word containing the second bit of each input word, etc. This is a time consuming process when done in software.
Some inventions handle this requirement by the provision of a specially designed memory into which image data words can be written in one direction and read out in an orthogonal direction. However, such special purpose memories are expensive, and tend to have a small capacity.
A method and circuit for producing these rotations at high speed without the necessity of special memory hardware is described in commonly owned patent applications Ser. No. 07/453,738 entitled "Method To Rotate A Bitmap image 90 Degrees", and Ser. No. 07/721,797, "Parallel Rotation Algorithm", which are incorporated by reference herein. In its simplest form, this prior invention can be described with reference to a 4 by 4 bit block of binary pixels in memory arranged as four horizontal words of four bits each, which must be rotated 90 degrees.
This prior method can be explained as the rotation of the bits within each 4 by 4 bit block and the rotation of the blocks of the whole image. First, the first word is loaded into the first line of a 4 by 4 bit buffer. The next word is circularly rotated one bit and loaded into the second line of the buffer. The third word is circularly shifted two bits and loaded into the third line of the buffer and the fourth line is circularly shifted three bits and loaded into the fourth line of the buffer. At this point a horizontal line in the original image is still a horizontal line in the buffer, but a vertical line in the original is now a diagonal line in the buffer.
Since the buffer is implemented from "by 1" devices, any bit in each device is addressable independently of the other devices, and a bit in one word in the buffer can be loaded into any of the four words of memory. Therefore if the bits in the buffer are addressed along diagonal lines parallel to the diagonal line in the buffer and loaded into single words of the memory, the diagonal line in the buffer will become a horizontal line at the output. Thus, the original vertical line is now horizontal. Continuing with addressing the bits along diagonal lines, a horizontal line in the buffer will become a diagonal line at the output. The output four words, prior to storage in memory, are shifted to line up the diagonal bits into a vertical line. Since this line started as a horizontal line, it can be seen that the 4 by 4 bit block has now been completely rotated 90 degrees. To rotate the blocks within the image, a simple addressing algorithm provides that the blocks read out of the block buffer are read into the correct area of a page buffer.
The above-described method relies on the idea that any one, but only one, bit from each of 4 memory devices can be accessed at one time. Therefore, if four vertical bits in a line are stored in one device, those four bits can never be output all at the same time, and a rotation that requires those bits to be formed into a horizontal line is impossible. However, if the vertical line is converted into a diagonal line (and the horizontal line is left horizontal) then each bit of each line resides in a different device, and the diagonal line, which originally was vertical, can be read out as a horizontal line.
The above-described method relies on a memory implemented from "by 1" devices, since, as described above, each bit in each device must be independently addressable. However, modern memory devices also include "by 4" devices, which means that every access outputs four bits in parallel, none of which are individually addressable: All four bits must come from the same address. What is required is a method that will perform this rotation in a memory implemented from such "by 4" devices.